#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class fourKeyBoard {
    unordered_map<vector<int>, int> memo;
public:
    int maxA(int n) {
        // dp(n, a_num, copy): 剩n次操作，已显示a_num个A，缓存区有copy个字符时，最多显示的A的数量
        return dp(n, 0, 0);
    }

    int dp(int n, int a_num, int copy) {
        if (n <= 0)
            return a_num;
        vector<int> t(3);
        t[0] = n;
        t[1] = a_num;
        t[2] = copy;

        if (memo.count(t))
            return memo[t];
        
        memo[t] = max( {
            dp(n - 1, a_num + 1, copy),     // A
            dp(n - 2, a_num, a_num),        // C-A, C-C
            dp(n - 1, a_num + copy, copy)   // C-V
        } );

        return memo[t];
    }
};

class fourKeyBoardBetter {
public:
    int maxA(int n) {
        int dp[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++)
                // 连续粘贴i - j次，屏幕上一共i - j + 1个重复的A组合
                dp[i] = max(dp[i], dp[j - 2] * (i - j + 1));
        }

        return dp[n];
    }
};

class twoKeyBoard {
public:
    int minSteps(int n) {
        int dp[n + 1];
        dp[0] = dp[1] = 0;
        // dp[i]: i个字符需要的最少操作
        // 贪心，每次都选最大的因数factor

        for (int i = 2; i <= n; i++) {
            for (int factor = i / 2; factor > 0; factor--) {
                if (i % factor == 0) {
                    dp[i] = dp[factor] + (i - factor) / factor + 1;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

class twoKeyBoardDivision {
public:
    int minSteps(int n) {
        // primes_division
        // n = a1 * a2 * a3 * ... * an
        int factor = 2;
        int ans = 0;
        while (n > 1) {
            while (n % factor == 0) {
                ans += factor;
                n /= factor;
            }
            factor++;
        }
        
        return ans;
    }
};